import React from 'react';
// 动态规划（或记忆化递归）
//自底向上：从 f(0) 和 f(1) 开始计算，逐步递推到 f(n)，避免递归的重复计算。
// 1、重叠子问题：问题可以分解为多个相似的子问题，且子问题会被重复计算
// 2、最优子结构：大问题的最优解可以由小问题的最优解推出（比如 f(10) 的最优解取决于 f(9) 和 f(8) 的最优解）
//3、无后效性：当前状态只与之前的状态有关，与之后的状态无关
// 步骤：确认状态f(1)表示什么-->明确递归关系-->初始化-->按顺序计算
// -------------------爬楼梯-------------------

// f1 = 1
// f2 = 2
// f3 = 3
// f4 = 1111 121 211 112 22 = 5
// f5 = 11111 2111 1211 1121 1112 221 212 122  = 8
// f6 = 111111 21111 12111 11211 11121 11112  2211 2112 1122 1212 2121 1221  222 = 13
// fn = f(n-1)+f(n-2)
const climbStairs = (n: number) => {
  if (n < 1) return 0;
  if (n === 1) return 1;
  if (n === 2) return 2;
  if (n > 2) return climbStairs(n - 1) + climbStairs(n - 2);
};
const climbStairs2 = (n: number) => {
  let p = 0,
    q = 0,
    r = 1;
  for (let i = 1; i <= n; i++) {
    q = p; //f(n-2)
    p = r; //f(n-1)
    r = p + q;
  }
  return r;
};

const climbStairs3 = (n: number) => {
  const dp: number[] = [];
  dp[0] = 1;
  dp[1] = 1;
  dp[2] = 2;
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n];
};

// ----------------杨辉三角---------------
const yhsj = (numRows: number) => {
  let result: number[][] = [[1]];
  for (let i = 1; i < numRows; i++) {
    // 遍历行 创建子数组
    let a = Array(i + 1).fill(1);
    for (let j = 0; j <= i; j++) {
      // 遍历列
      a[j] = (result[i - 1][j - 1] || 0) + (result[i - 1][j] || 0);
    }
    result.push(a);
  }
  return result;
};
const yhsj2 = (numrows: number) => {
  let result: number[][] = [[1]];
  for (let i = 1; i < numrows; i++) {
    let a = new Array(i + 1).fill(1);
    for (let j = 0; j <= i; j++) {
      a[j] = (result[i - 1][j - 1] || 0) + (result[i - 1][j] || 0);
    }
    result.push(a);
  }
  return result;
};
// --------------------打家劫舍-----------------
// dp[i]表示偷窃i间房最大金额
//偷窃第k间房时，不能偷窃第k-1间，那最大金额为k+dp[k-2];否则为dp[k-1]
//递归关系： dp[i] = max(nums[k]+dp[k-2],dp[k-1])  //考虑时先从最后开始考虑，实现时从前开始
//边界条件：dp[0]=nums[0],dp[1]=max(nums[0],nums[1])
const Robbery = (nums: number[]) => {
  const dp: number[] = new Array(nums.length);
  if (nums.length === 1) {
    return nums[0];
  }
  if (nums.length === 2) return Math.max(nums[0], nums[1]);
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  }
  return dp[nums.length - 1];
};
const djjs2 = (nums: number[]) => {
  const dp: number[] = [];
  dp[0] = nums[0];
  dp[1] = Math.max(nums[0], nums[1]);
  for (let i = 2; i < nums.length; i++) {
    dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
  }
  return dp[nums.length - 1];
};
//-----------------完全平方数-------------------
// 递归：  dp[i] = Math.min(dp[i], dp[i - s] + 1);s应当为所有n的平方和
const perfectSquare = (n: number): number => {
  // 边界条件
  if (n <= 3) return n;
  //square[i]:表示i最少的完全平方数
  const square = new Array(n + 1);
  square[0] = 0;
  square[1] = 1;
  square[2] = 2;
  square[3] = 3;
  square[4] = 1;
  for (let i = 5; i <= n; i++) {
    const k = Math.floor(Math.sqrt(i));
    // @@存在问题：只计算了第一次选择最大平方和、次大平方和
    square[i] = 1 + Math.min(square[i - k * k], square[i - (k - 1) * (k - 1)]);
  }
  return square[n];
};
const perfectSquare2 = (n: number): number => {
  // 边界条件：如果n本身就是完全平方数，直接返回1
  const root = Math.floor(Math.sqrt(n));
  if (root * root === n) return 1;

  // 初始化dp数组
  const dp = new Array(n + 1).fill(Infinity);
  dp[0] = 0;

  // 预处理所有完全平方数
  const squares: number[] = [];
  for (let i = 1; i * i <= n; i++) {
    squares.push(i * i);
  }

  // 动态规划填充
  for (let i = 1; i <= n; i++) {
    for (const s of squares) {
      if (s > i) break;
      // 每次计算选择当前平方和+dp[i - s]
      // 遍历所有对应的平方和
      dp[i] = Math.min(dp[i], dp[i - s] + 1);
    }
  }

  return dp[n];
};

const wqpf = (n: number) => {
  const dp = new Array(n + 1).fill(Infinity);
  dp[0] = 0;

  // 小于n的所有平方和
  const s: number[] = [];
  for (let i = 1; i * i <= n; i++) {
    s.push(i);
  }
  for (let i = 1; i <= n; i++) {
    for (let j of s) {
      if (i < j) break;
      dp[i] = Math.min(dp[i], dp[i - j] + 1);
    }
  }
  return dp[n];
};
// ----------------零钱补充----------------------
const extryCoins = (coins: number[], amount: number) => {
  const dp: number[] = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  // 硬币可以重复选择 则外层循环使用硬币 而不是amont
  // for (let i = 1; i <= amount; i++) {
  //   for (const c of coins) {
  //     if (c <= i && dp[i - c] != Infinity)
  //       dp[i] = Math.min(dp[i], dp[i - c] + 1);
  //   }
  // }
  // 完全背包

  for (const c of coins) {
    // 先遍历硬币
    for (let i = c; i <= amount; i++) {
      // 再遍历金额
      // 为什么什么dp[i-c] 每次i选择了c以后 得到i-c是否有选择方案
      // 如果 i < c，硬币 c 根本不能用于组成金额 i（因为 c > i），所以直接跳过这些情况可以减少无效计算。
      // 从可以选择c的金额开始到amunt 计算最小
      if (dp[i - c] !== Infinity) {
        dp[i] = Math.min(dp[i], dp[i - c] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
};

const testLQ = (coins: number[], amount: number) => {
  // 每次的最优解 dp[k] = Math.min(dp[i],dp[i-c]+1),每次选择一个coin得到的数量中的最小值
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let c of coins) {
    for (let a = 1; a <= amount; a++) {
      if (a >= c) {
        dp[a] = Math.min(dp[a], dp[a - c] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? 0 : dp[amount];
};
export default function index() {
  return (
    <div>
      动态规划:1、考虑最后一个的最优解： （1）只有两种情况选一个；单层遍历
      （2）多种情况选一个，使用双层遍历--谁可多选谁在外层
      2、解决时从小到大，使用数组记录计算过的结果
    </div>
  );
}
